#include <iostream>
#include <set>
#include <stack>
#include <map>
#include <algorithm>
using namespace std;

#define ALL(x) x.begin(), x.end()
#define INS(x) inserter(x, x.begin())
stack<int> s;
map<int, set<int> > Set;
map<set<int>, int> id;
int cnt;

int ID(set<int> t){
    if(!id.count(t)) {++cnt; id[t] = cnt; Set[cnt] = t; return cnt;}
    else return id[t];
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    int T; cin >> T;
    while(T--){
        int m; cin >> m;
        cnt = -1;
        while(m--){
            string in; cin >> in;
            switch (in[0]){
                case 'P':{
                    set<int> t;
                    s.push(ID(t));
                    break;
                }
                case 'D':{
                    s.push(s.top());
                    break;
                }
                case 'U':{
                    int t1 = s.top(); s.pop();
                    int t2 = s.top(); s.pop();

                    set<int> t;
                    set_union(ALL(Set[t1]), ALL(Set[t2]), INS(t));
                    s.push(ID(t));

                    id.erase(Set[t1]); Set.erase(t1);
                    id.erase(Set[t2]); Set.erase(t2);
                    break;
                }
                case 'I':{
                    int t1 = s.top(); s.pop();
                    int t2 = s.top(); s.pop();

                    set<int> t;
                    set_intersection(ALL(Set[t1]), ALL(Set[t2]), INS(t));
                    s.push(ID(t));

                    id.erase(Set[t1]); Set.erase(t1);
                    id.erase(Set[t2]); Set.erase(t2);
                    break;
                }
                case 'A':{
                    int t1 = s.top(); s.pop();
                    int t2 = s.top(); s.pop();

                    set<int> t = Set[t2];
                    t.insert(id[Set[t1]]);
                    s.push(ID(t));

                    id.erase(Set[t1]); Set.erase(t1);
                    id.erase(Set[t2]); Set.erase(t2);
                    break;
                }
            }
            cout << Set[s.top()].size() << "\n";
        }
        cout << "***\n";
    }
    return 0;
}